package medium;

/**
 * 给你一个长度为 n 的整数数组 nums 和 一个目标值 target。
 * 请你从 nums 中选出三个整数，使它们的和与 target 最接近。
 * 返回这三个数的和。假定每组输入只存在恰好一个解。
 *
 *  示例 1：
 * 输入：nums = [-1,2,1,-4], target = 1
 * 输出：2
 * 解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
 *
 *  示例 2：
 * 输入：nums = [0,0,0], target = 1
 * 输出：0
 *
 *  提示：
 *  3 <= nums.length <= 1000 
 *  -1000 <= nums[i] <= 1000 
 *  -104 <= target <= 104 
 *  
 *  Related Topics 数组 双指针 排序 
 *  👍 958 👎 0
 */

public class L16_最接近的三数之和 {
    public static void main(String[] args) {
        System.out.println(new L16_最接近的三数之和().threeSumClosest(new int[]{-3,-2,-5,3,-4}, -1));
    }

    /**
     * 暴力求解.
     * 执行耗时:312 ms,击败了5.00% 的Java用户
     * 内存消耗:38 MB,击败了68.99% 的Java用户
     */
    public int threeSumClosest(int[] nums, int target) {
        int len = nums.length;
        if (len < 3) return 0;

        int minGap = Integer.MAX_VALUE;
        int res = 0;

        for (int i=0; i<= len-3;i++){
            for (int j=i+1; j<=len-2; j++){
                for (int k = i+2; k<= len -1; k++){
                    if (i!=j && i!=k && j!=k){
                        int tmp = nums[i] + nums[j] + nums[k];
                        if (Math.abs(tmp - target) < minGap) {
                            minGap = Math.abs(tmp - target);
                            res = tmp;
                        }
                    }
                }
            }
        }
        return res;
    }
}
